package acwing_03;

import java.util.*;

public class _844_BFS_走迷宫 {
  
	static int n;// 行
	static int m;// 列
	static int[][] arr;// 迷宫
	static int[][] path;// 走过的路径
	
	// 用于存入Queue，保存坐标
	static class Pair{
		int x;
		int y;
		
		Pair (int x,int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		m = scan.nextInt();
		
		arr = new int[n][m];
		path = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		// 没走过的都为0
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				path[i][j] = 0;
			}
		}
		
		System.out.println(bfs());
		
		scan.close();
	}
	
	public static int bfs() {
		Queue<Pair> q = new LinkedList<Pair>();
		
		// 将起始节点放入Queue中
		Pair p = new Pair(0,0);
		q.add(p);
		
		// 用于上下左右移动的数字
		int dx[] = {-1,0,1,0};
		int dy[] = {0,1,0,-1}; 
		
		// 只要队列不为空则循环
		while(!q.isEmpty()) {
			// 弹出Queue对前面的元素（该元素会被移除并返回
			Pair point = q.poll();
			for(int i = 0; i < 4; i++) {
				int x = point.x + dx[i];
				int y = point.y + dy[i];
				// 对上下左右的元素进行判断
				// 如果未越界 arr[x][y] == 0 表示该格子是通的 path[x][y] == 0 表示该格式未走过，可以走
				if(x >= 0 && x < n && y >= 0 && y < m && arr[x][y] == 0 && path[x][y] == 0) {
					// 进入该格子，对其进行上一个节点的层数+1，表示从起点进入该格子的路径长度
					path[x][y] = path[point.x][point.y] + 1;
					// 将该格子元素放入Queue中
					Pair newNode = new Pair(x,y);
					q.add(newNode);
				}
			}
		}
		// 当所有的Queue都出完后，最终最后一格的path值就是从起点到终点的总长度
		return path[n-1][m-1];
	}

}
